#include "vector"
#include "iostream"

using namespace std;

class Solution169 {
public:
    int majorityElement(vector<int> &nums) {
        int most = nums[0];
        int count = 1;
        for (int i = 1; i < nums.size(); ++i) {
            if (most == nums[i]) count++;
            else {
                count--;
                if (count == 0) {
                    most = nums[++i];
                    count = 1;
                }
            }
        }
        return most;
    }
};